{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Knight’s Tour"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tourOfKnight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #巡逻的骑士"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个正整数 <code>m</code> 和 <code>n</code>&nbsp;，它们是一个 <strong>下标从 0 开始</strong> 的二维数组 <code>board</code> 的高度和宽度。还有一对正整数 <code>(r, c)</code> ，它们是骑士在棋盘上的起始位置。</p>\n",
    "\n",
    "<p>你的任务是找到一个骑士的移动顺序，使得&nbsp;<code>board</code>&nbsp;中每个单元格都 <strong>恰好</strong> 被访问一次（起始单元格已被访问，<strong>不应</strong> 再次访问）。</p>\n",
    "\n",
    "<p>返回数组 <code>board</code> ，其中单元格的值显示从 0 开始访问该单元格的顺序（骑士的初始位置为 0）。</p>\n",
    "\n",
    "<p>注意，如果 <code>0 &lt;= r2 &lt;= m-1 且 0 &lt;= c2 &lt;= n-1</code>&nbsp;，并且 <code>min(abs(r1-r2), abs(c1-c2)) = 1</code> 且 <code>max(abs(r1-r2), abs(c1-c2)) = 2</code>&nbsp;，则骑士可以从单元格 <code>(r1, c1)</code> 移动到单元格 <code>(r2, c2)</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>m = 1, n = 1, r = 0, c = 0\n",
    "<b>输出：</b>[[0]]\n",
    "<b>解释</b>只有一个单元格，骑士最初在其中，因此 1x1 网格中只有一个 0。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 4, r = 0, c = 0\n",
    "<b>输出：</b>[[0,3,6,9],[11,8,1,4],[2,5,10,7]]\n",
    "<b>解释：</b>按照以下移动顺序，我们可以访问整个棋盘。 \n",
    "(0,0)-&gt;(1,2)-&gt;(2,0)-&gt;(0,1)-&gt;(1,3)-&gt;(2,1)-&gt;(0,2)-&gt;(2,3)-&gt;(1,1)-&gt;(0,3)-&gt;(2,2)-&gt;(1,0)</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m,&nbsp;n &lt;= 5</code></li>\n",
    "\t<li><code>0 &lt;= r &lt;= m - 1</code></li>\n",
    "\t<li><code>0 &lt;= c &lt;= n - 1</code></li>\n",
    "\t<li>输入的数据保证在给定条件下至少存在一种访问所有单元格的移动顺序。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-knights-tour](https://leetcode.cn/problems/the-knights-tour/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-knights-tour](https://leetcode.cn/problems/the-knights-tour/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n0\\n0', '3\\n4\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        self.res, self.path, mn = [], [[-1] * n for i in range(m)], m * n\n",
    "        POS=((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2))\n",
    "        solve=False\n",
    "        def dfs(x,y,z):\n",
    "            nonlocal solve\n",
    "            self.path[x][y], z = z, z + 1\n",
    "            if z == mn: \n",
    "                solve=True\n",
    "                return\n",
    "            for dx, dy in POS:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1: \n",
    "                    dfs(nx,ny,z)\n",
    "                    if solve:\n",
    "                        return\n",
    "            if solve:\n",
    "                return\n",
    "            self.path[x][y] = -1\n",
    "        dfs(r,c,0)\n",
    "        return self.path\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 回溯\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        bd = [[-1 for j in range(n)] for i in range(m)]\n",
    "        find = False # 此变量表示是否已经找到解\n",
    "\n",
    "        def dfs(r,c,cur):\n",
    "            nonlocal find\n",
    "            bd[r][c] = cur # 先填当前格子\n",
    "            if cur == m*n-1: # 已经找到解，将find设为True，最快速度回到\n",
    "                find = True\n",
    "\n",
    "            if find: #找到解就不需要再搜了\n",
    "                return\n",
    "\n",
    "            nxtrc = [[r-1,c-2],[r-1,c+2],[r-2,c-1],[r-2,c+1],[r+1,c+2],[r+1,c-2],[r+2,c-1],[r+2,c+1]] # 8个跳法的顺序会直接影响输出结果，但本题只要找出任意解即可\n",
    "            for r1,c1 in nxtrc:\n",
    "                if not (0<=r1<m and 0<=c1<n) or bd[r1][c1]>-1: # 不能跳到出界位置或者跳过的格子\n",
    "                    continue\n",
    "\n",
    "                dfs(r1,c1,cur+1)\n",
    "\n",
    "            if not find: # 没有找到解，说明当前状态是死路，还原现场，回到上一个状态\n",
    "                bd[r][c]=-1\n",
    "        \n",
    "\n",
    "        dfs(r,c,0) \n",
    "        return bd\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 回溯\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        board = [[-1 for j in range(n)] for i in range(m)]\n",
    "        find = False # 此变量表示是否已经找到解\n",
    "\n",
    "        def dfs(r, c, cur):\n",
    "            nonlocal find\n",
    "            board[r][c] = cur # 先填当前格子\n",
    "            if cur == m*n-1: # 已经找到解，将find设为True，最快速度回到\n",
    "                find = True\n",
    "\n",
    "            if find: #找到解就不需要再搜了\n",
    "                return\n",
    "\n",
    "            nxtrc = [[r-1, c-2], [r-1, c+2], [r-2, c-1], [r-2, c+1], [r+1, c+2], [r+1, c-2], [r+2, c-1], [r+2, c+1]] # 8个跳法的顺序会直接影响输出结果，但本题只要找出任意解即可\n",
    "            for r1, c1 in nxtrc:\n",
    "                if not (0 <= r1 < m and 0 <= c1 < n) or board[r1][c1] != -1: # 不能跳到出界位置或者跳过的格子\n",
    "                    continue\n",
    "\n",
    "                dfs(r1, c1, cur+1)\n",
    "\n",
    "            if not find: # 没有找到解，说明当前状态是死路，还原现场，回到上一个状态\n",
    "                board[r][c] = -1\n",
    "        \n",
    "\n",
    "        dfs(r, c, 0) \n",
    "        return board\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        dirs=[[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]\n",
    "        self.ans=[[0]*n for _ in range(m)]\n",
    "        self.solve=False\n",
    "        def backtrack(x,y,k):\n",
    "            if k==0:\n",
    "                self.solve=True\n",
    "                return \n",
    "            for d in dirs:\n",
    "                dx=x+d[0]\n",
    "                dy=y+d[1]\n",
    "                if 0<=dx<m and 0<=dy<n and self.ans[dx][dy]==0 and (not (dx==r and dy==c)):\n",
    "                    self.ans[dx][dy]=m*n-k\n",
    "                    backtrack(dx,dy,k-1)\n",
    "                    if not self.solve:\n",
    "                        self.ans[dx][dy]=0\n",
    "            return \n",
    "        backtrack(r,c,m*n-1)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 回溯\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        bd = [[-1 for j in range(n)] for i in range(m)]\n",
    "        find = False # 此变量表示是否已经找到解\n",
    "\n",
    "        def dfs(r,c,cur):\n",
    "            nonlocal find\n",
    "            bd[r][c]=cur # 先填当前格子\n",
    "            if cur==m*n-1: # 已经找到解，将find设为True，最快速度回到\n",
    "                find = True\n",
    "\n",
    "            if find: #找到解就不需要再搜了\n",
    "                return\n",
    "\n",
    "            nxtrc = [[r-1,c-2],[r-1,c+2],[r-2,c-1],[r-2,c+1],[r+1,c+2],[r+1,c-2],[r+2,c-1],[r+2,c+1]] # 8个跳法的顺序会直接影响输出结果，但本题只要找出任意解即可\n",
    "            for r1,c1 in nxtrc:\n",
    "                if not (0<=r1<m and 0<=c1<n) or bd[r1][c1]>-1: # 不能跳到出界位置或者跳过的格子\n",
    "                    continue\n",
    "\n",
    "                dfs(r1,c1,cur+1)\n",
    "\n",
    "            if not find: # 没有找到解，说明当前状态是死路，还原现场，回到上一个状态\n",
    "                bd[r][c]=-1\n",
    "        \n",
    "        dfs(r,c,0) \n",
    "        return bd\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        self.res, self.path, mn = [], [[-1] * n for i in range(m)], m * n\n",
    "        POS=((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2))\n",
    "        def dfs(x,y,z):\n",
    "            self.path[x][y], z = z, z + 1\n",
    "            if z == mn: self.res = [lis[:] for lis in self.path]\n",
    "            elif not self.res:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1: \n",
    "                        dfs(nx,ny,z)\n",
    "            self.path[x][y] = -1\n",
    "        dfs(r,c,0)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "\n",
    "        bd = [[-1 for j in range(n)] for i in range(m)]\n",
    "        find = False # 此变量表示是否已经找到解\n",
    "\n",
    "        def dfs(r,c,cur):\n",
    "            nonlocal find\n",
    "            bd[r][c]=cur # 先填当前格子\n",
    "            if cur==m*n-1: # 已经找到解，将find设为True，最快速度回到\n",
    "                find = True\n",
    "            if find: #找到解就不需要再搜了\n",
    "                return\n",
    "            nxtrc = [[r-1,c-2],[r-1,c+2],[r-2,c-1],[r-2,c+1],[r+1,c+2],[r+1,c-2],[r+2,c-1],[r+2,c+1]] # 8个跳法的顺序会直接影响输出结果，但本题只要找出任意解即可\n",
    "            for r1,c1 in nxtrc:\n",
    "                if not (0<=r1<m and 0<=c1<n) or bd[r1][c1]>-1: # 不能跳到出界位置或者跳过的格子\n",
    "                    continue\n",
    "                dfs(r1,c1,cur+1)\n",
    "            if not find: # 没有找到解，说明当前状态是死路，还原现场，回到上一个状态\n",
    "                bd[r][c]=-1\n",
    "        \n",
    "        dfs(r,c,0) \n",
    "        return bd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        dirs=[[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]\n",
    "        self.ans=[[0]*n for _ in range(m)]\n",
    "        self.solve=False\n",
    "        def backtrack(x,y,k,r,c):\n",
    "            if k==0:\n",
    "                self.solve=True\n",
    "                return \n",
    "            for d in dirs:\n",
    "                dx=x+d[0]\n",
    "                dy=y+d[1]\n",
    "                if 0<=dx<m and 0<=dy<n and self.ans[dx][dy]==0 and (not (dx==r and dy==c)):\n",
    "                    self.ans[dx][dy]=m*n-k\n",
    "                    backtrack(dx,dy,k-1,r,c)\n",
    "                    if not self.solve:\n",
    "                        self.ans[dx][dy]=0\n",
    "            return \n",
    "        backtrack(r,c,m*n-1,r,c)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        has = {}\n",
    "        POS = ((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2))\n",
    "        self.res, self.path = [], [[-1] * n for i in range(m)]\n",
    "        mn = m * n\n",
    "        def dfs(x,y,z):\n",
    "            self.path[x][y], z = z, z + 1\n",
    "            if z == mn:\n",
    "                self.res = [lis[:] for lis in self.path]\n",
    "            elif not self.res:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1:\n",
    "                        dfs(nx,ny,z)\n",
    "            self.path[x][y] = -1\n",
    "        dfs(r,c,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        dirs=[[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        self.solve=False\n",
    "        def backtrack(x,y,k):\n",
    "            if k==0:\n",
    "                self.solve=True\n",
    "                return \n",
    "            for d in dirs:\n",
    "                dx=x+d[0]\n",
    "                dy=y+d[1]\n",
    "                if 0<=dx<m and 0<=dy<n and ans[dx][dy]==0 and (not (dx==r and dy==c)):\n",
    "                    ans[dx][dy]=m*n-k\n",
    "                    backtrack(dx,dy,k-1)\n",
    "                    if not self.solve:\n",
    "                        ans[dx][dy]=0\n",
    "            return \n",
    "        backtrack(r,c,m*n-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "      res=[[-1]*n for _ in range(m)]\n",
    "      mv=[(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]\n",
    "      ans=m*n-1\n",
    "      def dfs(x,y,l):\n",
    "        if l==ans:\n",
    "          return True\n",
    "        for tx,ty in mv:\n",
    "          nx=x+tx\n",
    "          ny=y+ty\n",
    "          if 0<=nx<m and 0<=ny<n and res[nx][ny]==-1:\n",
    "            res[nx][ny]=l+1\n",
    "            if dfs(nx,ny,l+1):return True\n",
    "            res[nx][ny]=-1\n",
    "        return False\n",
    "      res[r][c]=0\n",
    "      dfs(r,c,0)\n",
    "      return res\n",
    "      \n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 回溯\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        bd = [[-1 for j in range(n)] for i in range(m)]\n",
    "        find = False # 此变量表示是否已经找到解\n",
    "\n",
    "        def dfs(r,c,cur):\n",
    "            nonlocal find\n",
    "            bd[r][c] = cur # 先填当前格子\n",
    "            if cur == m*n-1: # 已经找到解，将find设为True，最快速度回到\n",
    "                find = True\n",
    "                return\n",
    "\n",
    "            if find: #找到解就不需要再搜了\n",
    "                return\n",
    "\n",
    "            nxtrc = [[r-1,c-2],[r-1,c+2],[r-2,c-1],[r-2,c+1],[r+1,c+2],[r+1,c-2],[r+2,c-1],[r+2,c+1]] # 8个跳法的顺序会直接影响输出结果，但本题只要找出任意解即可\n",
    "            for r1,c1 in nxtrc:\n",
    "                if not (0<=r1<m and 0<=c1<n) or bd[r1][c1]>-1: # 不能跳到出界位置或者跳过的格子\n",
    "                    continue\n",
    "\n",
    "                dfs(r1,c1,cur+1)\n",
    "\n",
    "            if not find: # 没有找到解，说明当前状态是死路，还原现场，回到上一个状态\n",
    "                bd[r][c]=-1\n",
    "        \n",
    "\n",
    "        dfs(r,c,0) \n",
    "        return bd\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def tourOfKnight(self, m, n, r, c):\n",
    "        res = [[0 for j in range(n)] for i in range(m)]\n",
    "        visited = [[0 for j in range(n)] for i in range(m)]\n",
    "        visited[r][c] = 1\n",
    "        self.f = False\n",
    "        d = [[-1, -2], [-1, 2], [1, -2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1]]\n",
    "\n",
    "        def helper(x, y, t):\n",
    "            if t == m * n - 1:\n",
    "                self.f = True\n",
    "                return\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == 0:\n",
    "                    visited[nx][ny] = 1\n",
    "                    res[nx][ny] = t + 1\n",
    "                    helper(nx, ny, t + 1)\n",
    "                    if self.f:\n",
    "                        return\n",
    "                    visited[nx][ny] = 0\n",
    "\n",
    "        helper(r, c, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        dir = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]\n",
    "        grid = [[-1] * n for _ in range(m)]\n",
    "        grid[r][c] = 0\n",
    "        mn = m * n\n",
    "        flag = False\n",
    "        ans = None\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        def f(i, j, idx):\n",
    "            nonlocal flag \n",
    "            nonlocal ans \n",
    "            if flag:\n",
    "                return \n",
    "            if idx == mn - 1:\n",
    "                flag = True\n",
    "                ans = copy.deepcopy(grid)\n",
    "                return \n",
    "            for dx, dy in dir:\n",
    "                nx, ny = i + dx, j + dy \n",
    "                if valid(nx, ny) and grid[nx][ny] == -1:\n",
    "                    grid[nx][ny] = idx + 1\n",
    "                    f(nx, ny, idx + 1)\n",
    "                    grid[nx][ny] = -1\n",
    "        \n",
    "        f(r, c, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        self.res, self.path, POS, mn = [], [[-1] * n for i in range(m)], ((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2)), m * n\n",
    "        def dfs(x,y,z):\n",
    "            self.path[x][y], z = z, z + 1\n",
    "            if z == mn: self.res = [lis[:] for lis in self.path]\n",
    "            elif not self.res:\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1: dfs(nx,ny,z)\n",
    "            self.path[x][y] = -1\n",
    "        dfs(r,c,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        g = [[-1] * n for _ in range(m)]\n",
    "        g[r][c] = 0\n",
    "        def recur(i, j, k):\n",
    "            if k == m * n:\n",
    "                return True\n",
    "            for x in range(1, 3):\n",
    "                y = (2, 1)[x-1]\n",
    "                for i1 in [i-x, i+x]:\n",
    "                    for j1 in [j-y, j+y]:\n",
    "                        if 0 <= i1 < m and 0 <= j1 < n and g[i1][j1] == -1:\n",
    "                            g[i1][j1] = k\n",
    "                            if recur(i1, j1, k+1):\n",
    "                                return True\n",
    "                            g[i1][j1] = -1\n",
    "            return False\n",
    "        recur(r, c, 1)\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def tourOfKnight1(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\r\n",
    "        mat = [[0] * n for _ in range(m)]\r\n",
    "        visited = [[False] * n for _ in range(m)]\r\n",
    "        visited[r][c] = True\r\n",
    "        flag = [False]\r\n",
    "        directions = [[-1, -2], [-1, 2], [1, -2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1]]\r\n",
    "\r\n",
    "        def helper(x, y, step):\r\n",
    "            if step == m * n - 1:\r\n",
    "                flag[0] = True\r\n",
    "                return\r\n",
    "            for dx, dy in directions:\r\n",
    "                xx, yy = x + dx, y + dy\r\n",
    "                if 0 <= xx < m and 0 <= yy < n and not visited[xx][yy]:\r\n",
    "                    visited[xx][yy] = True\r\n",
    "                    mat[xx][yy] = step + 1\r\n",
    "                    helper(xx, yy, step + 1)\r\n",
    "                    if flag[0]:\r\n",
    "                        return\r\n",
    "                    visited[xx][yy] = False\r\n",
    "\r\n",
    "        helper(r, c, 0)\r\n",
    "        return mat\r\n",
    "\r\n",
    "    # 回溯\r\n",
    "    def tourOfKnight2(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\r\n",
    "        ans = [[-1 for j in range(n)] for i in range(m)]\r\n",
    "        ans[r][c] = 0\r\n",
    "        direc = [\r\n",
    "            (-2,-1),(-2,1),\r\n",
    "            (-1,-2),(-1,2),\r\n",
    "            (1,-2),(1,2),\r\n",
    "            (2,-1),(2,1)\r\n",
    "        ]\r\n",
    "        uu = [[-1 for j in range(n)] for i in range(m)] # 收集答案\r\n",
    "        valid = False \r\n",
    "        def dfs(i,j,steps):\r\n",
    "            nonlocal valid\r\n",
    "            if valid: return  # 只需要找到一个解就返回，加速\r\n",
    "            ans[i][j] = steps \r\n",
    "            if steps == m*n-1 and not valid: # 收集答案\r\n",
    "                valid = True # 补丁\r\n",
    "                for i in range(m):\r\n",
    "                    for j in range(n):\r\n",
    "                        uu[i][j] = ans[i][j]\r\n",
    "                    \r\n",
    "            for di in direc:\r\n",
    "                new_i = i + di[0]\r\n",
    "                new_j = j + di[1]\r\n",
    "                if 0<=new_i<m and 0<=new_j<n and ans[new_i][new_j]==-1:\r\n",
    "                    dfs(new_i,new_j,steps+1)\r\n",
    "\r\n",
    "            ans[i][j] = -1\r\n",
    "        \r\n",
    "        dfs(r,c,0)\r\n",
    "        return uu\r\n",
    "        \r\n",
    "    # dfs\r\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\r\n",
    "        self.res, self.path, POS, mn = [], [[-1] * n for i in range(m)], ((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2)), m * n\r\n",
    "        def dfs(x,y,z):\r\n",
    "            self.path[x][y], z = z, z + 1\r\n",
    "            if z == mn: self.res = [lis[:] for lis in self.path]\r\n",
    "            elif not self.res:\r\n",
    "                for dx, dy in POS:\r\n",
    "                    nx, ny = x + dx, y + dy\r\n",
    "                    if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1: dfs(nx,ny,z)\r\n",
    "            self.path[x][y] = -1\r\n",
    "        dfs(r,c,0)\r\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "from copy import deepcopy\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param m:\n",
    "        :param n:\n",
    "        :param r:\n",
    "        :param c:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        line = [0] * n\n",
    "        grid = []\n",
    "        total = m * n\n",
    "        for i in range(m):\n",
    "            grid.append(line.copy())\n",
    "        dq1 = SortedList(key=lambda x: -len(x[1]))\n",
    "        dq1.add(((r, c), [(r, c)]))\n",
    "        action = [(1, 2), (1, -2), (-1, -2), (-1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)]\n",
    "\n",
    "        def get_idx(r, c):\n",
    "            return r * (n) + c\n",
    "\n",
    "        def getpos(flist):\n",
    "            grid2 = deepcopy(grid)\n",
    "            for k, v in enumerate(grid):\n",
    "                for k2, v2 in enumerate(v):\n",
    "                    idx1 = get_idx(k, k2)\n",
    "                    tag = flist.index(idx1)\n",
    "                    grid2[k][k2] = tag\n",
    "            return grid2\n",
    "\n",
    "        while dq1:\n",
    "            first, path = dq1.pop(0)\n",
    "            if len(path) == total:\n",
    "                return getpos([get_idx(i[0], i[1]) for i in path])\n",
    "            for i in action:\n",
    "                newidx = first[0] + i[0], first[1] + i[1]\n",
    "                if 0 <= newidx[0] < m and 0 <= newidx[1] < n and newidx not in path:\n",
    "                    path1 = path.copy()\n",
    "                    path1.append(newidx)\n",
    "                    dq1.add((newidx, path1))\n",
    "        return []\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
